\section{The previous procedure: a brief overview}

The procedure described in~\cite{Correa14} generates valid inequalities
for $STAB(G)$ of the form $c^\top x \leq \alpha(G, c)$,
where $c \in \mathbb{N}^n$, and $\alpha(G, c) = \max
\{ c^\top x \mid$ $x \in STAB(G) \}$. It is based on the following operation,
which adds edges (called {\em false edges}) to $G$ in order to create a
projected graph in a way that generalizes the edge projection explored in~\cite{Pardalos,Rossi.Smriglio.01}.
For all $v \in V$, define $N(v) := \{ w \in V \mid vw \in E
\}$.

\begin{definition}[Clique Projection~\cite{LovaszPlummer86}]
Let $W \subseteq V$, $|W| \geq 2$, be a clique in $G$. The {\em clique
projection} of $W$ gives the graph $G \mid W = (V, E \mid W)$ in which $E\mid W
= E \cup \{ vw \not\in E \mid W \subseteq N(v) \cup N(w) \}$.
\end{definition}

The generation of a valid inequality consists of the
following two steps, illustrated respectively in Fig.~\ref{fig:projection} and
Fig.~\ref{fig:lifting}.

\begin{figure}[htb]
\centering
        \begin{subfigure}[$G_0$ ($= G$ by definition).]{
			\quad\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{graphExample2}
\draw		(2) 	to[out=40,in=140] (5);
			\end{tikzpicture}\quad}
        \end{subfigure}\quad\quad
        \begin{subfigure}[$G_3$ ($=G_2$ in this example).]{
\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
\shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
(2.south east) -- (3.base) -- (3.south) -- cycle;
\node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 
\shade[rounded corners=1ex,fill=blue,above] (1.north) -- (3.south east) --
(3.base) -- (4.base) -- (4.south west) -- cycle;
\node[text=blue,text opacity=1] at +(0,-1) {$W_2$}; 
\shade[rounded corners=1ex,fill=green,above] (1.north east) to[out=30,in=-120]
(5.south west) -- (4.base) -- (4.south) -- cycle;
\node[text=olive,text opacity=1] at +(3,0) {$W_3$}; 

			\input{graphExample2}
\draw		(2) 	to[out=40,in=140] (5);

\draw[very thick,color=red]		(5) 	to[out=145,in=35] (6);
\draw[very thick,color=red]		(4) 	-- (5);
\draw[very thick,color=red]		(4) 	-- (6);

\draw[very thick,color=blue]	(2) 	to[out=30,in=150] (7);
\draw[very thick,color=blue]	(5) 	to[out=150,in=30] (7);
\draw[very thick,color=blue]	(2) 	to[out=35,in=145] (8);
%\draw[very thick,color=blue]	(2) 	to[out=40,in=140] (5);
\end{tikzpicture}}
        \end{subfigure}
\caption{Projected graph $G_3$ (with false
edges) is obtained after projecting $W_1 = \{ 1, 2, 3 \}$, $W_2 = \{ 1, 3, 4
\}$, and $W_3 = \{ 1, 4, 5 \}$, in this order.}
\label{fig:projection}
\end{figure}

\noindent\textbf{Step 1: Sequence of clique projections.} Define $G_0 := G$
and determine distinct subsets $W_1, \ldots, W_r$ of $V$ such that, for
every $t \in \{ 1, \ldots, r \}$, $W_t$ is a clique of $G_{t-1}$ and $G_t$ is
the projected graph $G_{t-1} \mid W_t$.

\noindent\textbf{Step 2: Sequence of clique lifting operations.}
\label{sec:clique-lift} Let $W_{r+1} \subseteq V$ be a clique of
$G_r$ and, for all $W \subseteq V$, define $x_W := \sum_{v \in W} x_v$. The lifting
procedure starts with the clique inequality $g_r(x) = x_{W_{r+1}} \leq 1$, which
is valid for $STAB(G_r)$, and iteratively for $t=r-1, \ldots, 0$ generates
$g_t(x) = g_{t+1}(x) + \gamma_{t+1} (x_{W_{t+1}} - 1) \leq 1$, which is valid
for $STAB(G_t)$ (for an example, see
Fig.~\ref{sfig:cl1}--\ref{sfig:cl2}--\ref{sfig:cl3}). In the expression for
$g_t(x)$, $\gamma_{t+1}$ stands for $\alpha(G_t[V \setminus W_{t+1}], \Gamma_{t+1}) -
\sum_{i=t+2}^r \gamma_i - 1$, where $\Gamma_{t+1}$ is the vector of
coefficients of $g_{t+1}(x)$. Note that $\gamma_{t+1}$ is obtained by
maximizing $g_{t+1}(x) - \sum_{i=t+2}^r \gamma_i - 1$ over the set $\left\{ x \in STAB(G_t) \mid x_{W_{t+1}} = 0 \right\}$.

% 
% \begin{figure}[htb]
% \centering
%         \begin{subfigure}[{$x[2] + x[6] + x[7] +
%         {\setlength{\fboxsep}{1pt}\colorbox{green}{1}}x[8] + x[5] \leq 1$
%         is valid for $G_2$ since $\lambda_3 = 0$}.]{ 
%         \begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
% \shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
% (2.south east) -- (3.base) -- (3.south) -- cycle;
% \node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 
% \shade[rounded corners=1ex,fill=blue,above] (1.north) -- (3.south east) --
% (3.base) -- (4.base) -- (4.south west) -- cycle;
% \node[text=blue,text opacity=1] at +(0,-1) {$W_2$}; 
% \shade[rounded corners=1ex,fill=green,above] (1.north east) to[out=30,in=-120]
% (5.south west) -- (4.base) -- (4.south) -- cycle;
% \node[text=green,text opacity=1] at +(3,0) {$W_3$}; 
% \shade[rounded corners=1ex,fill=orange,above] (2.north west) --
% (5.north east) -- (5.south east) -- (2.south west) -- cycle;
% 
% 			\input{graphExample}
% 
% \node[vertex,ball color=green,opaque] (8) at (3.0,3.0) {8};
% 
% \draw[very thick,color=red]		(5) 	to[out=135,in=45] (6);
% \draw[very thick,color=red]		(4) 	-- (6);
% 
% \draw[very thick,color=blue]	(2) 	to[out=30,in=150] (7);
% \draw[very thick,color=blue]	(5) 	to[out=150,in=30] (7);
% \draw[very thick,color=blue]	(2) 	to[out=45,in=135] (8);
% \draw[very thick,color=blue]	(2) 	to[out=60,in=120] (5);
% \end{tikzpicture}}
%         \end{subfigure}
%         \begin{subfigure}[Lifting
%         {${\setlength{\fboxsep}{1pt}\colorbox{blue}{1}}x[2] + x[6] + {\setlength{\fboxsep}{1pt}\colorbox{blue}{1}}x[7] + x[8] + {\setlength{\fboxsep}{1pt}\colorbox{blue}{1}}x[5] \leq 1$} with
%         $\lambda_2 = 2$ results in {$x[2] + x[6] + x[7] + x[8] + x[5] + 2x[1] + 2x[3] +
%         2x[4] \leq 3$}, valid for $G_1$.]{ 
%         \begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
% \shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
% (2.south east) -- (3.base) -- (3.south) -- cycle;
% \node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 
% \shade[rounded corners=1ex,fill=blue,above] (1.north) -- (3.south east) --
% (3.base) -- (4.base) -- (4.south west) -- cycle;
% \node[text=blue,text opacity=1] at +(0,-1) {$W_2$}; 
% \shade[rounded corners=1ex,fill=orange,above] (2.north west) --
% (5.north east) -- (5.south east) -- (2.south west) -- cycle;
% 
% 			\input{graphExample}
%  
% \node[vertex,ball color=blue,opaque] (2) at (-6.0,3.0) {2};
% \node[vertex,ball color=blue,opaque] (7) at (0,3.0) {7};
% \node[vertex,ball color=blue,opaque] (5) at (6.0,3.0) {5};
% 
% \draw[very thick,color=red]		(5) 	to[out=135,in=45] (6);
% \draw[very thick,color=red]		(4) 	-- (6);
% \end{tikzpicture}}
%         \end{subfigure}
%         \begin{subfigure}[{$x[2] +
%         {\setlength{\fboxsep}{1pt}\colorbox{red}{1}}x[6] + x[7] + x[8] + x[5] +
%         2x[1] + 2x[3] + {\setlength{\fboxsep}{1pt}\colorbox{red}{2}}x[4] \leq 3$
%         is also valid for $G_0$ since $\lambda_1 = 0$}.]{ 
%         \begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
% \shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
% (2.south east) -- (3.base) -- (3.south) -- cycle;
% \node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 
% \shade[rounded corners=1ex,fill=orange,above] (2.north west) --
% (5.north east) -- (5.south west) to[out=-120,in=30] (1.north east) -- (1.north
% west) to[out=150,in=-60] (2.south east) -- cycle;
% 
% 			\input{graphExample}
%  
% \node[vertex,ball color=red,opaque] (4) at (1.5,0) {4};
% \node[vertex,ball color=red,opaque] (6) at (-3.0,3.0) {6};
% \end{tikzpicture}}
%         \end{subfigure}
% \caption{Example of a sequence of clique liftings starting with the clique
% inequality of $\{ 2, 5, 6, 7, 8 \}$ to generate $x[2] +
% x[6] + x[7] + x[8] + x[5] + 2x[1] + 2x[3] + 2x[4] \leq 3$.}
% \label{fig:lifting}
% \end{figure}
